#include "stdlib.h"
#include "assert.h"
#include "err.h"
#include "heap.h"

/* Estructura del TAD */
struct sheap{
        halpha* arreglo; 
	int tam;		
	int max_tam;
};

/* Constructor del TAD */
heap create_heap(const size_t max){
	heap h;
	assert(max > 0);
	h = (heap)calloc(1,sizeof(struct sheap));
	if (h != NULL){
		h->arreglo = (halpha*)calloc(max,sizeof(halpha));
		if (h->arreglo != NULL){
			h->tam = 0;
			h->max_tam = max;
		}
		else{
			free(h);
			h = NULL;
                        errx(EXIT_FAILURE,"No hay memoria disponible");
		}
        }
        else errx(EXIT_FAILURE,"No hay memoria disponible");
	return h;
}

/* Añadir elemento al Heap */
void add_heap(heap h, halpha e){     
	assert(h != NULL);
	assert(!heap_lleno(h));
        h->arreglo[h->tam] = e;
	h->tam = h->tam + 1;
	flotar(h,h->tam - 1);
}

/* Retorna el primer elemento del Heap */
halpha top_heap(heap h) {
	assert(h != NULL);
	assert(!heap_vacio(h));
	return h->arreglo[0];
}

/* Quita el primer elemento del Heap */
void heap_pop(heap h){
	assert(h != NULL);
	assert(!heap_vacio(h));	
	h->arreglo[0] = h->arreglo[h->tam - 1];
	h->tam = h->tam - 1;
	if (h->tam > 0) sink(h,0);
}

/* Su estado es 1 si el Heap se encuentra vacío */
Bool heap_vacio(heap h){
	assert(h != NULL);
	return (h->tam == 0);
}

/* Su estado es 1 si el Heap se encuentra lleno */
Bool heap_lleno(heap h){
	assert(h != NULL);
	return (h->tam == h->max_tam);
}

/* Quitar elemento del Heap */
halpha heap_saca(heap h){
	halpha elemento;
	assert(h != NULL);
	assert(!heap_vacio(h));
	elemento = h->arreglo[h->tam - 1];
	h->tam = h->tam - 1;
	return elemento;
}

/* Retorna el tam actual del Heap */
int tam_heap(heap h){
	assert(h != NULL);
	return (h->tam);
}

/* Destructor del TAD */
heap heap_destroy(heap h){
	assert(h != NULL);
	free(h->arreglo);
        h->arreglo = NULL;
	free(h);
        h = NULL;
	return h;
}

/* Desarrollamos aquí las funciones secundarias */

void flotar(heap h,int i){
	int flotante;
	assert(h != NULL);
        assert(i >= 0);
	assert(i < h->tam);
	flotante = i;
	while (has_father(flotante) && must_lift(h,flotante)) {
		lift(h,flotante);
		flotante = father(flotante);
	}
}

void lift(heap h,int i){
	halpha auxiliar;
	assert(h != NULL);
	assert(i >= 0);
	assert(i < h->tam);
	auxiliar = h->arreglo[i];
	h->arreglo[i] = h->arreglo[father(i)];
	h->arreglo[father(i)] = auxiliar;
}

int father(int i){
	assert(has_father(i));
	return ((i - 1) / 2);
}

int left_child(int i){
	assert(i >= 0);
	return (2 * i + 1);
}

int right_child(int i){
	assert(i >= 0);
	return (2 * i + 2);
}

Bool has_father(int i){
	assert(i >= 0);
	return (i != 0);
}

Bool has_child(heap h,int i){
	assert(h != NULL);
	assert(i >= 0);
	assert(i < h->tam);
	return (left_child(i) < h->tam);
}

Bool has_children(heap h,int i){
	assert(h != NULL);
	assert(i >= 0);
	assert(i < h->tam);
	return (right_child(i) < h->tam);
}

Bool must_lift(heap h,int i){
	Bool b;
	assert(h != NULL);
	assert(i >= 0);
	assert(i < h->tam);
	b = FALSE;
	if (has_father(i)) b = (peso(h->arreglo[i]) < peso(h->arreglo[father(i)]));
	return b;
}

int min_child(heap h,int i){
	int minimo;
	assert(h != NULL);
	assert(has_child(h,i));
	minimo = left_child(i);
	if (has_children(h,i) && peso(h->arreglo[right_child(i)]) < peso(h->arreglo[left_child(i)])) minimo = right_child(i);
	return minimo;
}

void sink(heap h,int i){
	int auxiliar;
	assert(h != NULL);
	assert(i >= 0);
	assert(i < h->tam);
	auxiliar = i;
	while (has_child(h,auxiliar) && must_lift(h,min_child(h,auxiliar))){
		auxiliar = min_child(h,auxiliar);
		lift(h,auxiliar);
	}
}
